Batch 1 - Class 09 - Combinatorics (2)

Pre-class problems:

We are back to three black and two white hats, and every person can see the other two people. At every bell, whoever knows his hat color has to announce it. What will happen, and how quickly will everyone have announced their hat color?
(MC Chap2, Prob 14) In how many ways can you place a white and a black king on a chessboard so that they can't capture each other?

Attendance Muskaan, Smiti, Sumati, Yashvi, Manas, Ishartek, Anisha, Tara

Class puzzles

Hat pre-class puzzle
Answer: If there are two people wearing white hats, on the first bell, the third person will announce that he know color of his hat (black), and on the next bell, the other two, having seen what the third person said, will announce that they have white hats. If there is one person with white hat, and two with black, on the first bell, no one will announce anything. On the next bell, people with black hat (who can see one white hat) will each announce that they have a black hat (otherwise someone would have seen two white hats and announced at first bell). On the third bell, the remaining person will announce the white hat.If all three have white hats, no one will announce on first two bells, but all three will realize that everyone must have a white hat at the third bell (otherwise one of the top two scenarios would have happened), and everyone will simultaneously announce on third bell.

Instructor Notes: http://mesosyn.com/mental1-1c-ans.html

Combinatorics

Note: The symbol "." is used as a multiplication sign below

Principal 1: If the thing we are counting is an outcome of a multistage process, then the number of outcomes is the product of the number of choices for each stage

Principal 2: If the thing we are counting can happen in different exclusive ways, then the number of outcomes is the sum of the number of outcomes through each way

Pre-class Problem (MC Chap2, Prob 14) In how many ways can you place a white and a black king on a chessboard so that they can't capture each other?
Answer: 3612 (4.60+24.58+36.55)

Instructor Notes: First insight is that the number of squares attacked depends on the position of the king. Second, kids should correctly "add" the different scenarios.

(BerkeleyMC Chap 2 - Prob 10) How many even three digit numbers are there with no repeating digits?
328

Instructor Notes: First take through all 3 digit numbers (900). Then 3 digit numbers with no repeating digits (9.9.8). Hint on the problem (1) Lets start with rightmost digit instead of leftmost. (2) Lets separate the cases where 0 is the rightmost digit versus not. Make sure kids understand the addition of two cases. (BerkeleyMC has a good analysis)

Principal 3: Counting the complement requires subtraction

(BerkeleyMC Chap 2 - Prob 12) Three different flavors of pie are available, and seven children are given a slice of pie so that at least two children get different flavors. How many ways can this be done?
Answer: 3.3.3.3.3.3.3 - 3 = 2184

Instructor Notes: Explain the problem clearly, for example aaaabbc is one possibility. Then calculate number of possibilities without a constraint (3.3.3.3.3.3.3). Then exclude cases. Make sure kids understand why subtraction happens.

(MC Chap 2- Prob 46) We toss the dice three times. How many possible outcomes with at least one occurrence of 6
(6.6.6 - 5.5.5)

Instructor Notes: Ensure kids understand the subtraction

Hat Problem - (Problem 5 "Dark Consequences" Dozen Hats (Dropbox)) - 100 progressive visible men, each with red or purple, with at least one purple. Each can say "pass" or "I have purple". Game wins if at least one says "I have purple" correctly, and none gets it wrong. What is the strategy
Answer: First one to see no purples in front should say "I have purple"

Picture Phrases: (Kids' contributed) - Guess the phrases that the following pictures represent

Answer: (1) The long and short of IT (2) Think outside the box (3) Last in, first out (4) Underwear (5) Above the line (6) I Understand

Homework Problem: (Khan Academy - Togglers) There are four togglers (a Toggler alternately tells the truth and lies) and one truthteller in a room. Ask two question (both to same person, or one each to different people) to determine who is the truthteller.
Answer: Ask to same guy, "Are you the truthteller", "Who is the truthteller" if Answer is Yes, and "Who is not a truthteller" if Answer is No

References:

Mathematical Circles (Russian Experience), by Dmitri Fomin, Sergey Genkin, Ilia Itenberg

A Decade of the Berkeley Math Circle. The American Experience, Volume 1. Zvezdelina Stankova, Tom Rike

Hat Puzzles http://mesosyn.com/mental1-1c-ans.html

A Dozen Hat Problems, by Ezra Brown and James Tanton